An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem

摘要

The Traveling salesman problem (TSP) is proved to be NP-complete in mostcases. The genetic algorithm (GA) is one of the most useful algorithms forsolving this problem. In this paper a conventional GA is compared with animproved hybrid GA in solving TSP. The improved or hybrid GA consist ofconventional GA and two local optimization strategies. The first strategy isextracting all sequential groups including four cities of samples and changingthe two central cities with each other. The second local optimization strategyis similar to an extra mutation process. In this step with a low probability asample is selected. In this sample two random cities are defined and the pathbetween these cities is reversed. The computation results show that theproposed method also finds better paths than the conventional GA within anacceptable computation time.